package Offer.offer2019;

import domain.TreeNode;

import java.util.LinkedList;

/**
 * 重建二叉树
 * 输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
 * @author: leiwenkang02@meituan.com
 * @date: 2019/4/17
 * @time: 20:16
 */
public class Offer06 {
    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode head = new Offer06().rebuildTreeNode(pre, in);

        //层序遍历
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(head);
        while (!list.isEmpty()) {
            TreeNode p = list.remove();
            System.out.println(p.val);
            if (p.left != null) {
                list.add(p.left);
            }

            if (p.right != null) {
                list.add(p.right);
            }
        }

    }

    //递归
    public TreeNode rebuildTreeNode(int[] pre, int[] in) {
        if (pre == null || pre.length == 0 || in == null || in.length == 0) {
            return null;
        }
        return rebuildTreeNode(pre, in, 0, pre.length -1, 0, in.length - 1);
    }

    private TreeNode rebuildTreeNode(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        //根节点
        int val = pre[preStart];
        TreeNode head = new TreeNode(val);
        //在中序遍历序列中查找根节点
        int index = inStart;
        while (index <= inEnd) {
            if (in[index] == val) {
                break;
            }
            index++;
        }

        head.left = rebuildTreeNode(pre, in, preStart + 1, preStart + index - inStart, inStart, index - 1);
        head.right = rebuildTreeNode(pre, in, preStart + index - inStart + 1, preEnd, index + 1, inEnd);

        return head;
    }
}
